home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Diamond Collection / The Diamond Collection (Software Vault)(Digital Impact).ISO / cdr47 / lzpip103.zip / UNLZW.C < prev    next >
Text File  |  1994-02-24  |  9KB  |  297 lines
  1. /* unlzw.h - this is part of the Tar program (see file define.h) */
  2.  
  3. #include <stdio.h>
  4. #include "modern.h"
  5. #include "lzpipe.h"
  6. #include "lzwbits.h"
  7.  
  8. #ifdef MODERN
  9. #    include <stdlib.h>
  10. #else
  11.     char *malloc();
  12.     void free();
  13. #endif
  14.  
  15. static int d_n_bits;    /* number of bits/code */
  16. static int hashbits  = BITS;
  17. static int d_maxbits = BITS;    /* user settable max # bits/code */
  18. static code_int d_maxcode;    /* maximum code, given n_bits */
  19. /* should NEVER generate this code */
  20. static code_int d_maxmaxcode = (code_int)1 << BITS;
  21.  
  22. #ifdef XENIX_16
  23.   static unsigned short *decodet[MAXPAGES] = { NULL };
  24.   static char_type *stab[NUMPAGES];
  25.  
  26. # define tab_prefixof(i) (decodet[(int)((i) >> PAGEXP)][(int)(i) & PAGEMASK])
  27. # define tab_suffixof(i) (stab[(int)((i) >> PAGEXP)][(int)(i) & PAGEMASK])
  28. #else
  29.   static unsigned short *decodet = NULL;
  30.   static char_type *stab;
  31.  
  32. # define tab_prefixof(i) decodet[i]
  33. # define tab_suffixof(i) stab[i]
  34. #endif
  35.  
  36. static char_type *de_stack = NULL; /* output stack */
  37. static code_int d_free_ent = 0;
  38.  
  39. /* block compression parameters -- after all codes are */
  40. /* used up, and compression rate changes, start over.  */
  41. static int d_block_compress = BLOCK_MASK;
  42. static int d_clear_flg = 0;
  43. static count_int d_checkpoint = CHECK_GAP;
  44.  
  45. #ifdef LZFILE
  46.     FILE *lzw_inp_port = NULL;
  47. #    define getbyte() getc(lzw_inp_port)
  48. #else
  49.     int (*lzw_inp_port)__ARGS__((void)) = NULL;
  50. #    define getbyte() (*lzw_inp_port)()
  51. #endif
  52.  
  53. static int getpiece __ARGS__((char *, int));
  54.  
  55. static int getpiece(buf, nbytes)
  56. char buf[]; int nbytes;
  57. {
  58.    register i, b;
  59.  
  60.    for (i=0; i<nbytes && (b=getbyte())!=EOF; i++) buf[i] = b;
  61.    return i;
  62. }
  63.  
  64. static code_int getcode __ARGS__((void))
  65. /* Read one code, returns -1 on EOF */
  66. {
  67. #ifndef vax
  68.    static char_type rmask[] = {0x00,0x01,0x03,0x07,0x0f,0x1f,0x3f,0x7f};
  69. #endif
  70. /* On the VAX, it is important to have the register declarations */
  71. /* in exactly the order given, or the asm will break. */
  72.    register code_int code;
  73.    static int offset = 0, size = 0;
  74.    static char_type buf[BITS];
  75.    register int r_off, bits;
  76.    register char_type *bp = buf;
  77.  
  78.    if (d_clear_flg > 0 || offset >= size || d_free_ent > d_maxcode ) {
  79.       /*
  80.        * If the next entry will be too big for the current code
  81.        * size, then we must increase the size.  This implies reading
  82.        * a new buffer full, too.
  83.        */
  84.       if (d_free_ent > d_maxcode) {
  85.          d_maxcode = ++d_n_bits == d_maxbits ?
  86.                         d_maxmaxcode : MAXCODE(d_n_bits);
  87.       }
  88.       if (d_clear_flg > 0) {
  89.          d_maxcode = MAXCODE(d_n_bits = INIT_BITS);
  90.          d_clear_flg = 0;
  91.       }
  92.       if ((size = getpiece((char *)buf, d_n_bits)) <= 0) return -1; /* EOF */
  93.       offset = 0;
  94.       /* Round size down to integral number of codes */
  95.       size = (size << 3) - (d_n_bits - 1);
  96.    }
  97.    r_off = offset;
  98.    bits = d_n_bits;
  99. #ifdef vax
  100.    asm( "extzv      r10,r9,(r8),r11" );
  101. #else
  102.    /* Get to the first byte. */
  103.    bp += (r_off >> 3);
  104.    r_off &= 7;
  105.    /* Get first part (low order bits) */
  106.    code = char_to_byte((unsigned)(*bp++)) >> r_off;
  107.    r_off = 8 - r_off;    /* now, offset into code word */
  108.    if ((bits -= r_off) >= 8) {
  109.       /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  110.       code |= char_to_byte((unsigned)(*bp++)) << r_off;
  111.        r_off += 8;
  112.        bits -= 8;
  113.    }
  114.    /* high order bits. */
  115.    code |= (unsigned)(*bp & rmask[bits]) << r_off;
  116. #endif
  117.    offset += d_n_bits;
  118.    return code;
  119. }
  120.  
  121. int lzwmark(wishbits)
  122. int wishbits;
  123. {
  124. #ifdef XENIX_16
  125.    register i, j; code_int l;
  126. #endif
  127.    code_int dhsize = _HSIZE;
  128.  
  129.    if (de_stack) return hashbits;
  130.    if (wishbits > BITS) wishbits = BITS;
  131.    hashbits = wishbits;
  132.  
  133.    de_stack = (char_type *)malloc(sizeof(char_type) * 8000);
  134.    if (!de_stack) return -1;
  135.    if      (wishbits >= 16) dhsize = 69001L;
  136.    else if (wishbits >= 15) dhsize = 35023L;
  137.    else if (wishbits >= 14) dhsize = 18013L;
  138.    else if (wishbits >= 13) dhsize = 9001L;
  139.    else                     dhsize = 5003L;
  140. #ifdef XENIX_16
  141.    for (l=(code_int)1<<wishbits, i=0; i<NUMPAGES && l>0; i++) {
  142.       j = l<PAGESIZE ? (int)l : PAGESIZE;
  143.       stab[i] = (char_type *)malloc(sizeof(char_type) * j);
  144.       if (!stab[i]) return -1;
  145.       l -= j;
  146.    }
  147.    for (l=dhsize, i=0; i<MAXPAGES && l>0; i++) {
  148.       j = l > PAGESIZE ? PAGESIZE : (int)l;
  149.       decodet[i] = (unsigned short *)malloc(sizeof(unsigned short)*j);
  150.       if (!decodet[i]) break;
  151.       l -= j;
  152.    }
  153.    l = dhsize - l;
  154.    if      (l >= 69001L) { j = 16; dhsize = 69001L; }
  155.    else if (l >= 35023L) { j = 15; dhsize = 35023L; }
  156.    else if (l >= 18013)  { j = 14; dhsize = 18012L; }
  157.    else if (l >= 9001)   { j = 13; dhsize =  9001L; }
  158.    else if (l >= 5003)   { j = 12; dhsize =  5003L; }
  159.    else return -1;
  160.    if (hashbits > j) hashbits = j;
  161. #else
  162.    if ((decodet=(unsigned short*)malloc(sizeof(*decodet)*dhsize))==NULL ||
  163.        (stab   =(char_type *)malloc(sizeof(*stab) * (1<<wishbits))) == NULL)
  164.       return -1;
  165. #endif
  166.    return hashbits;
  167. }
  168.  
  169. void lzwrelease()
  170. {
  171. #ifdef XENIX_16
  172.    register i;
  173. #endif
  174.  
  175.    if (de_stack != NULL) {
  176.       free((char*)de_stack); de_stack = NULL;
  177. #ifdef XENIX_16
  178.       for (i=0; i<NUMPAGES && stab[i]!=NULL; i++) free((char*)(stab[i]));
  179.       if (i >= NUMPAGES) {
  180.          for (i=0; i<MAXPAGES && decodet[i]!=NULL; i++)
  181.             free((char*)(decodet[i]));
  182.       }
  183. #else
  184.       if (decodet != NULL) {
  185.          free((char*)decodet);
  186.          if (stab != NULL) free((char*)stab);
  187.       }
  188. #endif
  189.    }
  190. }
  191.  
  192. /* This routine adapts to the codes in the file building the "string" table */
  193. /* on-the-fly; requiring no table to be stored in the compressed file.      */
  194.  
  195. static notfirst = 0;
  196. static char_type *stackp;
  197. static code_int oldcode;
  198. static int finchar;
  199.  
  200. int lzwopen(lzw_inp)
  201. #ifdef LZFILE
  202.     FILE *lzw_inp;
  203. #else
  204.     int (*lzw_inp)__ARGS__((void));
  205. #endif
  206. {
  207.    register k;
  208.  
  209.    lzw_inp_port = lzw_inp;
  210.    d_clear_flg  = 0;
  211.    d_checkpoint = CHECK_GAP;
  212.  
  213.    if (getbyte() != LZW_0TH_MAGIC || getbyte() != LZW_1ST_MAGIC) return -1;
  214.  
  215.    d_maxbits = getbyte(); /* set -b from file */
  216.    d_block_compress = d_maxbits & BLOCK_MASK;
  217.    d_maxbits &= BIT_MASK;
  218.    if ((k = lzwmark(d_maxbits)) < d_maxbits) {
  219.       lzw_inp_port = NULL;
  220.       return k<INIT_BITS ? INIT_BITS-1 : k;
  221.    }
  222.    d_maxmaxcode = (code_int)1 << d_maxbits;
  223.    /* As above, initialize the first 256 entries in the table. */
  224.    d_maxcode = MAXCODE(d_n_bits = INIT_BITS);
  225.    for (k = 255; k >= 0; k--) {
  226.       tab_prefixof(k) = 0;
  227.       tab_suffixof(k) = (char_type)k;
  228.    }
  229.    d_free_ent = d_block_compress ? FIRST : 256;
  230.    stackp = de_stack;
  231.    finchar = (int)(oldcode = getcode());
  232.    notfirst = 0;
  233.    return 0;
  234. }
  235.  
  236. int lzwread(buf, len)
  237. char buf[];
  238. unsigned len;
  239. {
  240.    static code_int code, incode;
  241.    register k = 0;
  242.  
  243.    if (!notfirst) {
  244.       if (!lzw_inp_port) return (lzerror=ZNOPEN, -1);
  245.       notfirst = 1;
  246.       /* EOF already? Get out of here */
  247.       if (oldcode == -1) goto end;
  248.       /* first code must be 8 bits = char */
  249.       ++k; *buf++ = (char)finchar;
  250.    }
  251.    for (;;) {
  252.       if (stackp == de_stack) {
  253.          if ((code = getcode()) < 0) break;
  254.          if (code == CLEAR && d_block_compress) {
  255.             for (code=255; code >= 0; code--) tab_prefixof(code) = 0;
  256.             d_clear_flg = 1;
  257.             d_free_ent = FIRST - 1;
  258.             if ((code = getcode()) == -1) break; /* O, untimely death! */
  259.          }
  260.          incode = code;
  261.          /* Special case for KwKwK string. */
  262.          if (code >= d_free_ent) {
  263.             if (code > d_free_ent) return (lzerror=ZMOULD, -1);
  264.             *stackp++ = finchar;
  265.             code = oldcode;
  266.          }
  267.          /* Generate output characters in reverse order */
  268. #ifdef SIGNED_COMPARE_SLOW
  269.          while ((unsigned long)code >= (unsigned long)256)
  270. #else
  271.          while (code >= 256)
  272. #endif
  273.          {
  274.             *stackp++ = tab_suffixof(code);
  275.             code = tab_prefixof(code);
  276.          }
  277.          *stackp++ = finchar = tab_suffixof(code);
  278.       }
  279.       /* And put them out in forward order */
  280.       do {
  281.          if (k >= len) goto end;
  282.          ++k; *buf++ = *--stackp;
  283.       } while (stackp > de_stack);
  284.  
  285.       /* Generate the new entry. */
  286.       if ((code=d_free_ent) < d_maxmaxcode) {
  287.          tab_prefixof(code) = (unsigned short)oldcode;
  288.          tab_suffixof(code) = finchar;
  289.          d_free_ent = code+1;
  290.       }
  291.       /* Remember previous code. */
  292.       oldcode = incode;
  293.    }
  294. end:
  295.    return k;
  296. }
  297.